#include "big_int.h"

big_int::big_int()
{
	shift = 0;
};

big_int::big_int(const std::string &str)
{
	for (int i = str.length(); i > 0; i-= base_length)
	{
		if (i >= base_length)
		{
			digits.push_back(atoi(str.substr(i - base_length, base_length).c_str()));
		}
		else
		{
			digits.push_back(atoi(str.substr(0, i).c_str()));
		}
	}
	shift = 0;
};

big_int::big_int(long long n)
{
	if (n == 0)
	{
		digits.push_back(0);
	}
	while (n > 0)
	{
		digits.push_back(n % base);
		n /= base_length;
	}
	shift = 0;
};

big_int::big_int(const std::vector<long long> &vect)
{
	if (vect.empty())
	{
		digits = std::vector<long long>(1, 0);
	}
	else
	{
		digits = vect;
	}
	shift = 0;
	remove_zeroes();
};

void big_int::remove_zeroes()
{
	while ((digits.size() > 1) && (digits.back() == 0))
	{
		digits.pop_back();
	}
};

void big_int::restore()
{
	for (int i = 0; i < static_cast<int>(digits.size()); i++)
	{
		if (digits[i] >= 0)
		{
			long long tr = digits[i] / base;
			digits[i] %= base;
			if (tr > 0)
			{
				if (i < static_cast<int>(digits.size() - 1))
				{
					digits[i + 1] += tr;
				}
				else
				{
					digits.push_back(tr);
				}
			}
		}
		else
		{
			long long tr = - digits[i] / base;
			if (digits[i] % base != 0)
			{
				tr ++;
			}
			if (i < static_cast<int>(digits.size() - 1))
			{
				digits[i + 1] -= tr;
			}
			digits[i] += tr * base;
		}
	}
};

long long big_int::compare(const big_int &num)
{
	int temp = digits.size() - num.digits.size();
	if (shift + temp != num.shift)
		return temp + shift - num.shift;

	if (temp > 0)
	{
		int i = digits.size() - 1;
		while ((i > temp) && (digits[i] == num.digits[i - temp]))
			i--;
		if (i >= temp)
			return digits[i] - num.digits[i - temp];
		while (i >= 0)
		{
			if (digits[i] != 0)
				return 1;
			i--;
		}
	}
	else
	{
		int i = num.digits.size() - 1;
		while ((i > -temp) && (digits[i + temp] == num.digits[i]))
			i--;
		if (i >= -temp)
			return digits[i + temp] - num.digits[i];
		while (i >= 0)
		{
			if (num.digits[i] != 0)
				return 1;
			i--;
		}
	}

	return 0;
};

big_int& big_int::operator = (const big_int& number)
{
	digits = number.digits;
	shift = number.shift;
	return *this;
};

big_int& big_int::operator -= (const big_int& number)
{
	if (shift > number.shift)
	{
		digits.insert(digits.begin(), shift - number.shift, long long(0));
		shift = number.shift;
	}
	long long shift_ = number.shift - shift;
	for (int i = 0; i < static_cast<int>(number.digits.size()); i++)
	{
		digits[i + static_cast<int>(shift_)] -= number.digits[i];
	}
	restore();
	remove_zeroes();
	return *this;
};

big_int& big_int:: operator*= (const int& number)
{
	if (number == 0)
	{
		*this = 0;
	}
	else
	{
		for (int i = 0; i < static_cast<int>(digits.size()); i++)
		{
			digits[i] *= number;
		}
		restore();
	}
	return *this;
};

big_int operator * (const big_int& a, const int& b)
{
	big_int bignum = a;
	int num = b; 

	if (num == 0)
	{
		bignum = 0;
	}
	else
	{
		for (int i = 0; i < static_cast<int>(bignum.digits.size()); i++)
		{
			bignum.digits[i] *= num;
		}
		bignum.restore();
	}
	return bignum;
};

bool big_int::operator == (const big_int& number)
{
	return compare(number) == 0;
};

long long big_int::find_divider(const big_int& number)
{
	if (compare(number) < 0)
	{
		return 0;
	}
	int left = 0;
	int right = base;
	int middle;
	while (left != right - 1)
	{
		middle = (left + right) / 2;
		if (compare(number * middle) >= 0)
		{
			left = middle;
		}
		else
		{
			right = middle;
		}
	}
	return left;
};
 
std::pair <big_int, big_int> big_int::operator / (const big_int& number)
{
	std::vector <long long> quotient;
	std::vector <long long> remainder;

	big_int num = number;
	int tmp = digits.size() - number.digits.size();
	num.shift += tmp;
	while (compare(number) >= 0)
	{
		long long temp = find_divider(num);
		quotient.push_back(temp);
		*this -= num * static_cast<int>(temp);
		num.shift--;
	}
	std::reverse(quotient.begin(), quotient.end());

	if (num.shift >= 0)
	{
		quotient.insert(quotient.begin(), num.shift + 1, long long(0));
	}
	return std::make_pair(big_int(quotient), *this);
};

int length(const int& number)
{
	if (number == 0)
		return 1;
	int num = number;
	int length_ = 0;
	while (num > 0) 
	{
		num /= 10;
		length_ ++;
	}
	return length_;
};

std::istream& operator >> (std::istream& is, big_int& number)
{
	std::string str;
	if (is >> str)
	{
		number = big_int(str);
	}
	return is;
};

std::ostream& operator << (std::ostream& os, big_int& number)
{
	for (int i = number.digits.size() - 1; i >= 0; i--)
	{
		int zero = big_int::base_length - length(static_cast<int>(number.digits[i]));
		if (i < static_cast<int>(number.digits.size() - 1))
		{
			for (int j = 0; j < zero; j++)
			{
				os << '0'; 
			}
		}
		os << number.digits[i];
	}
	return os;
};

